import sun.reflect.generics.tree.Tree;

import java.util.ArrayDeque;
import java.util.Deque;

public class BSTIterator173 {
    Deque<TreeNode> deque = new ArrayDeque<>();
    TreeNode p = null;

    public BSTIterator173(TreeNode root) {
        p = root;
    }

    public int next() {
        while (hasNext()) {
            deque.push(p);
            p = p.left;
        }
        p = deque.pop();
        int cur = p.val;
        p = p.right;
        return cur;
    }

    public boolean hasNext() {
        return !deque.isEmpty() || p != null;
    }
}

